package com.as3.timbot.data.collections
{
	public class PQueue
	{
	var heap:Array;
	var map:Object;
	var idInc:Number;
	var max_num:Number;

	//Written by Branden Hall
	//Modified by Jobe Makar
	//Ported to ActionScript 2.0 by Jobe Makar
	//Ported to AS3 by Tim Willison
	
		public function PQueue() 
		{
			heap = new Array();
			map = new Object();
			idInc = 0;
			max_num = 1000000;
		}
		// insert items into the queue
		public function insert(obj:Object, priority:Number):Number
		{
			if (!obj) {
				return 0;
			}
			var pos:Number = heap.length;
			var temp:Object = new Object();
			var id:Number = idInc++;
			temp.priority = priority;
			temp.data = obj;
			temp.id = id;
			temp.pos = pos;
			map[id] = temp;
			heap[pos] = temp;
			$filterUp(pos);
			//
			heap.splice(max_num);
			return id;
		}
		
		public function setLimit(max:Number):void
		{
			max_num = max;
		}
		
		// get the value of the top priority w/o removing it
		//get front..........t.w.
		public function getTop():Number {
			return heap[0].priority;
		}
		
		// remove, and return, the top element in the heap
		//dequeue.........t.w.
		public function removeTop():Object
		{
			if (heap.length>0) {
				var result:Object = heap[0].data;
				
				//delete map[heap[0].id];//...........t.w
				map[heap[0].id]=null;
				//delete heap[0];//.......t.w
				heap[0] = heap[heap.length-1];
				heap[0].pos = 0;
				heap.splice(heap.length-1, 1);
				$filterDown(0);
				return result;
			} else {
				trace("returning a null object from heap");
				return new Object();////////////////total hack, ugh....t.w.
			}
		}
	
		// reprioritize an element
		//reprioritize..........t.w.
		public function setPriority(id, value) {
			var element = map[id];
			var pos:Number = element.pos;
			var oldPriority:Number = element.priority;
			element.priority = value;
			if (oldPriority>element.priority) {
				$filterUp(pos);
			} else {
				$filterDown(pos);
			}
		}
		
		// return the priority of an element
		// can do this at the prioritizable class....t.w.
		public function getPriority(id) 
		{
			return map[id].priority;
		};
		
		// determine if the queue is empty
		// use getSize.........t.w.
		public function isEmpty():Boolean
		{
			return (heap.length == 0);
		};
		
		// get priority of top element
		//get front() returns element, then access 'priority' at prioritizable class...t.w.
		public function getTopPriority() 
		{
			return heap[0].priority;
		};
		
		// check to see if an ID is in the queue
		// use contains()..........t.w.
		public function isQueued(id):Boolean
		{
			return (map[id] != null);
		};
		
		// remove an object from the queue
		// remove().........t.w.
		public function remove(id) 
		{
			if (isQueued(id)) {
				var index:Number = map[id].pos;
				delete map[id];
				delete heap[index];
				heap[index] = heap[heap.length-1];
				heap[0].pos = 0;
				heap.splice(heap.length-1, 1);
				return true;
			} else {
				return false;
			}
		};
		//-----------------------------------------------------------
		// Private "helper" methods
		//-----------------------------------------------------------
		private function $filterUp(index:Number):void
		{
			var i:Number = index;
			while (i>0 && heap[int((i-1)/2)].priority>heap[i].priority) {
				var parent:Number = Math.floor((i-1)/2);
				var temp = heap[i];
				heap[i] = heap[parent];
				heap[parent] = temp;
				heap[i].pos = i;
				heap[parent].pos = parent;
				i = parent;
			}
		};
		
		private function $filterDown(index:Number):void
		{
			var i:Number = index;
			var left:Number, right:Number, k:Number;
			if (i<(heap.length-1)/2) {
				left = 2*i+1;
				right = 2*i+2;
				if (right>=heap.length) {
					k = left;
					right = left;
				} else {
					if (heap[left].priority<heap[right].priority) {
						k = left;
					} else {
						if (heap[left].priority == heap[right].priority) {
							if (heap[left].id<heap[right].id) {
								k = left;
							} else {
								k = right;
							}
						} else {
							k = right;
						}
					}
				}
				var temp:Object = new Object();////tw
				if (heap[i].priority>heap[k].priority) {
					temp = heap[i];///t.w.
					heap[i] = heap[k];
					heap[k] = temp;
					heap[i].pos = i;
					heap[k].pos = k;
					$filterDown(k);
				} else {
					if (heap[i].priority == heap[k].priority) {
						if (heap[i].id>heap[k].id) {
							temp = heap[i];////tw
							heap[i] = heap[k];
							heap[k] = temp;
							heap[i].pos = i;
							heap[k].pos = k;
							$filterDown(k);
						}
					}
				}
			}
		}
	}
}